package org.usmile.algorithms.leetcode.middle;

import java.util.ArrayDeque;

/**
 * 695. 岛屿的最大面积
 *
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 *
 * 示例 1：
 *
 *
 * 输入：grid =
 * [
 * [0,0,1,0,0,0,0,1,0,0,0,0,0],
 * [0,0,0,0,0,0,0,1,1,1,0,0,0],
 * [0,1,1,0,1,0,0,0,0,0,0,0,0],
 * [0,1,0,0,1,1,0,0,1,0,1,0,0],
 * [0,1,0,0,1,1,0,0,1,1,1,0,0],
 * [0,0,0,0,0,0,0,0,0,0,1,0,0],
 * [0,0,0,0,0,0,0,1,1,1,0,0,0],
 * [0,0,0,0,0,0,0,1,1,0,0,0,0]
 * ]
 * 输出：6
 * 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 * 示例 2：
 *
 * 输入：grid = [[0,0,0,0,0,0,0,0]]
 * 输出：0
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] 为 0 或 1
 */
public class _0695 {
}

class _0695_Solution {
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private int rows;

    private int cols;

    private boolean[][] visited;

    private int[][] grid;

    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        rows = grid.length;
        cols = grid[0].length;
        visited = new boolean[rows][cols];

        int maxArea = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 1 && !visited[row][col]) {
                    maxArea = Math.max(dfs(row, col), maxArea);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int row, int col) {
        visited[row][col] = true;
        if (grid[row][col] == 0) {
            return 0;
        }
        int area = 1;
        for (int[] direction : DIRECTIONS) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];
            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                if (!visited[nextRow][nextCol]) {
                    area += dfs(nextRow, nextCol);
                }
            }
        }

        return area;
    }
}

class _0695_Solution1 {
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int maxArea = 0;
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 1 && !visited[row][col]) {
                    int area = 0;
                    visited[row][col] = true;
                    stack.push(new int[]{row, col});
                    while (!stack.isEmpty()) {
                        area++;
                        int[] curr = stack.poll();
                        for (int[] direction : DIRECTIONS) {
                            int nextRow = curr[0] + direction[0];
                            int nextCol = curr[1] + direction[1];
                            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                                if (grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                                    visited[nextRow][nextCol] = true;
                                    stack.push(new int[]{nextRow, nextCol});
                                }
                            }
                        }
                    }

                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }
}

class _0695_Solution2 {
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int maxArea = 0;
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 1 && !visited[row][col]) {
                    int area = 0;
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                    while (!queue.isEmpty()) {
                        area++;
                        int[] curr = queue.poll();
                        for (int[] direction : DIRECTIONS) {
                            int nextRow = curr[0] + direction[0];
                            int nextCol = curr[1] + direction[1];
                            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                                if (grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                                    visited[nextRow][nextCol] = true;
                                    queue.offer(new int[]{nextRow, nextCol});
                                }
                            }
                        }
                    }

                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }
}

